package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1719 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * Hard 睡大觉
     * @return:
     */
    class Solution {
        public int checkWays(int[][] pairs) {
            //1. 构建图
            Map<Integer, Set<Integer>> graph = new HashMap<>();
            for (int[] pair : pairs) {
                graph.putIfAbsent(pair[0], new HashSet<>());
                graph.putIfAbsent(pair[1], new HashSet<>());
                graph.get(pair[0]).add(pair[1]);
                graph.get(pair[1]).add(pair[0]);
            }
            int n = graph.keySet().size();
            int root = -1;
            //2. 所有人的祖先就是先祖（唐太祖，只有最上面那一辈叫祖）
            for (int key : graph.keySet()) {
                int size = graph.get(key).size();
                if (size == n - 1) {
                    root = key;
                }
            }

            if (root == -1)
                return 0;

            int ans = 1;
            for (Integer node : graph.keySet()) {
                if (node == root) continue;
                Set<Integer> neighbours = graph.get(node);
                int size = graph.get(node).size();
                int parent = -1;
                int pSize = Integer.MAX_VALUE;
                //3. 找自己的爹，和自己关联的后代比自己多的可能是自己爹，也可能是先祖
                //爹就刚刚好跟我关联，且后辈比我多，比祖宗少（宗代表先辈非最上一辈）
                for (Integer neighbour : neighbours) {
                    if (graph.get(neighbour).size() < pSize && size <= graph.get(neighbour).size()) {
                        parent = neighbour;
                        pSize = graph.get(neighbour).size();
                    }
                }

                if (parent == -1)
                    return 0;

                //3. 既然跟我关联的，确认了爹，那其他要么是兄弟，要么是子女，要么是祖宗
                //那我爹的先辈后辈，必然包含了我的先辈后辈（我的后辈应该比父辈少）
                Set<Integer> tmp = new HashSet<>(graph.get(parent));
                tmp.add(parent);
                //4. 如果不能完全包含，说明父子关系不成立
                if (!tmp.containsAll(neighbours))
                    return 0;
                //5. 父子关系成立，不一定谁父谁子，那如果有结果，那就不止一种
                // 注意不能直接返回，其他点验证不通过的情况，可能返回0
                if (pSize == size) {
                    ans = 2;
                }
            }
            return ans;
        }
    }


    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC1719 an = new LC1719();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
